package com.cium.aqie.highOrderFunction

/**
 * @Function: 尾递归
 * @Author: aqie
 * @Date: 2019/9/2 9:35
 */
// 定义链表
data class ListNode(val value: Int, var next: ListNode? = null)

/**
 * 递归查找链表
 * 调用自身后没有其他操作 ： 尾递归
 * 关键字优化：编译器把代码变成迭代
 */
tailrec fun findListNode(head: ListNode?, value: Int): ListNode?{
    head?: return  null
    if(head.value == value) return head
    return findListNode(head.next, value)
}

/**
 * 求阶乘， 不是尾递归
 */
fun factorial(n: Long): Long{
    return n * factorial(n - 1)
}

data class TreeNode(val value: Int){
    var left: TreeNode? = null
    var right: TreeNode? = null
}

/**
 * 不算尾递归
 */
fun findTreeNode(root: TreeNode?, value: Int): TreeNode?{
    root?: return null
    if(root.value == value) return root
    // 左子树没有就返回右子树递归
    return findTreeNode(root.left, value)?: return findTreeNode(root.right, value)
}

fun main(args: Array<String>) {
    val MAX_NODE_COUNT = 100000
    val head = ListNode(0)
    var p = head
    for(i in 1.. MAX_NODE_COUNT){
        p.next = ListNode(i)
        p = p.next!!
    }
    // 查找倒数第三个
    println(findListNode(head, MAX_NODE_COUNT - 2)?.value)
}